package com.leetcodehot.problems;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class problems17 {
    /**
     * 子集型回溯：
     * 一、每个元素可以选与不选
     *      不选：直接跳过
     *      选：加上影响 下一步 撤销影响
     *      退出条件：最终才是答案比如长度到了n
     *
     *      伪代码：
     *      dfs(){
     *          if(i == n){
     *              ans.append(path);
     *              return;
     *          }
     *          //不选
     *          dfs(i+1);
     *
     *          //选
     *          path.append(xx[i]);
     *          dfs(i+1);
     *          path.pop();
     *      }
     * 二、站在答案的角度考虑，第一个部分选谁 第二个部分选谁
     *      可能需要剔除掉重复的，所以可能要规定顺序
     *      每一次都是合法答案。
     *      伪代码：
     *      private void dfs(int i) {
     *         if (i == digits.length) {
     *             ans.add(new String(path));
     *             return;
     *         }
     *         for (char c : MAPPING[digits[i] - '0'].toCharArray()) {
     *             path[i] = c; // 直接覆盖
     *             dfs(i + 1);
     *             //如果有撤销 要记得
     *             //path.pop()
     *         }
     *     }
     *
     */
    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    private final List<String> ans = new ArrayList<>();
    private char[] digits;
    private char[] path;

    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        if (n == 0) {
            return new ArrayList<>();
        }
        this.digits = digits.toCharArray();
        path = new char[n]; // 注意 path 长度一开始就是 n，不是空数组
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == digits.length) {
            ans.add(new String(path));
            return;
        }
        for (char c : MAPPING[digits[i] - '0'].toCharArray()) {
            path[i] = c; // 直接覆盖
            dfs(i + 1);
        }
    }
}
